/*************************************************************************
 * File Name:    Restore_IP_Addresses.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Sat 02 Nov 2013 03:21:49 PM CST
 * 
 * Description:  
 |-----------------------------------------------------------------------
 | Problem: Restore IP Addresses
 |
 | Given a string containing only digits, restore it by returning all
 | possible valid IP address combinations.
 |
 | For example:
 | Given "25525511135",
 | return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)
 |-----------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iomanip>

using namespace std;

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        if (s.size() > 12) return vector<string>();
        vector<string> ans;
        string t;
        int seg[4], p;
        char tmp[20];
        
        for (size_t i = 1; i <= 3 && i + 3 <= s.size(); ++i) {
            for (size_t j = 1; j <= 3 && i + j + 2 <= s.size(); ++j) {
                for (size_t k = 1; k <= 3 && i + j + k + 1 <= s.size(); ++k) {
                    t = s.substr(0, i) + "." + s.substr(i, j) + "." + s.substr(i + j, k) + "." + s.substr(i + j + k);
                    sscanf(t.c_str(), "%d.%d.%d.%d", &seg[0], &seg[1], &seg[2], &seg[3]);
                    for (p = 0; p < 4; ++p) {
                        if (seg[p] >= 0 && seg[p] <= 255) continue;
                        else break;
                    }
                    if (sprintf(tmp, "%d%d%d%d", seg[0], seg[1], seg[2], seg[3]) != s.size() || p < 4) continue;
                    
                    ans.push_back(t);
                }
            }
        }
        return ans;
    }
};
